package com.leetcode;

/**
 * 479. 最大回文数乘积
 */
public class Solution479 {

    public int largestPalindrome(int n) {
        int upper = (int)Math.pow(10, n) - 1;
        int lower = (int)Math.pow(10, n - 1);
        int max = -1;
        // 两个循环到数据量太大，会超时
        for (int i = upper; i >= lower; i--) {
            for (int j = upper; j >= lower; j--) {
                int num = i * j;
                if (isPalindrome(num)) {
                    max = Math.max(max, num);
                }
            }
        }
        return max % 1337;
    }

    private boolean isPalindrome(int num) {
        String str = String.valueOf(num);
        int p = 0;
        int q = str.length() - 1;
        while (p < q) {
            if (str.charAt(p) != str.charAt(q)) {
                return false;
            }
            p++;
            q--;
        }
        return true;
    }

    public static void main(String[] args) {
        int res = new Solution479().largestPalindrome(3);
        System.out.println(res);
    }
}
